#include "gtest/gtest.h"
#include <string>
#include "findstring.h"
#include "stdexcept"
#include "Timer.hpp"
#include <fstream>
using namespace std;

ofstream out("result.txt");

string GetRandomABMillionOneString()
{
    string result;
    srand(0);
    for (int i = 0; i < 1000001; ++i)
    {
        result += (rand() < RAND_MAX/2) ? 'a' : 'b';
    }
    return result;
}

TEST (TestFindString, EmptyString)
{
    string _string = "", subString = "";
    EXPECT_THROW(FindString(_string, subString), logic_error);
}

TEST (TestFindString, SingleCharSubString)
{
    string _string = "abcabc", subString = "a";
    list<string::const_iterator> expected;
    expected.push_back(_string.begin());
    expected.push_back(_string.begin() + 3);
    list<string::const_iterator> actual = FindString(_string, subString);
    ASSERT_EQ(expected, actual);
}

TEST (TestFindString, Simple)
{
    string _string = "abcaabc", subString = "ab";
    list<string::const_iterator> expected;
    expected.push_back(_string.begin());
    expected.push_back(_string.begin() + 4);
    list<string::const_iterator> actual = FindString(_string, subString);
    ASSERT_EQ(expected, actual);
}

TEST (TestFindString, General)
{
    string _string = "ababab", subString = "abab";
    list<string::const_iterator> expected;
    expected.push_back(_string.begin());
    expected.push_back(_string.begin() + 2);
    list<string::const_iterator> actual = FindString(_string, subString);
    ASSERT_EQ(expected, actual);
}


TEST(ComputePrefixFunctionTests, EmptyString)
{
    ASSERT_EQ(vector<size_t>(), ComputePrefixFunction(""));
}

TEST(ComputePrefixFunctionTests, SingleCharString)
{
    string str = "a";
    vector<size_t> expected(str.length());
    ASSERT_EQ(expected, ComputePrefixFunction(str));
}

TEST(ComputePrefixFunctionTests, NonrepetablePrefixString)
{
    string str = "abcd";
    vector<size_t> expected(str.length());
    ASSERT_EQ(expected, ComputePrefixFunction(str));
}

TEST(ComputePrefixFunctionTests, SimpleString)
{
    string str = "ababab";
    vector<size_t> expected(str.length());
    expected[1 - 1] = 0;
    expected[2 - 1] = 0;
    expected[3 - 1] = 1;
    expected[4 - 1] = 2;
    expected[5 - 1] = 3;
    expected[6 - 1] = 4;
    ASSERT_EQ(expected, ComputePrefixFunction(str));
}



TEST (PerformanceTests, abk_ab1000kString)
{
    string _string, subString;
    IStopwatch *z = createStopwatch();
    out << "\nabk_ab1000kString\n";
    for (int j = 0; j < 2; ++j)
    {
        if (j == 0)
        {
            out << "\nTrivial\n";
        }
        else
        {
            out << "\nKMP\n";
        }

        out << "\n[";
        for (int k = 1; k <= 101; k += 10)
        {
            _string = "";
            subString = "";
            for (int i = 0; i < k; ++i)
            {
                subString += "ab";
                for (int i = 0; i < 1000; ++i)
                {
                    _string += "ab";
                }
            }
            z->reset();
            z->start();
            if (j == 0)
            {
                FindStringTrivial(_string, subString);
            }
            else
            {
                FindStringKMP(_string, subString);
            }
            z->stop();
            out << "[" << k << "," << z->getElapsed() << "],";
        }
        out << "]";
    }
}


TEST (PerformanceTests, am_abRandomString)
{
    string _string, subString;
    IStopwatch *z = createStopwatch();
    _string = GetRandomABMillionOneString();
    out << "\nam_abRandomString\n";
    for (int j = 0; j < 2; ++j)
    {
        if (j == 0)
        {
            out << "\nTrivial\n";
        }
        else
        {
            out << "\nKMP\n";
        }

        out << "[";
        for (int m = 1; m <= 1000001; m += 10000)
        {
            subString = "";
            for (int i = 0; i < m; ++i)
            {
                subString += "a";
            }
            z->reset();
            z->start();
            if (j == 0)
            {
                FindStringTrivial(_string, subString);
            }
            else
            {
                FindStringKMP(_string, subString);
            }
            z->stop();
            out << "[" << m << "," << z->getElapsed() << "],";
        }
        out << "]";
    }
}



TEST (PerformanceTests, aaaaa_aaaaabhString)
{
    string _string, subString = "aaaaa";
    IStopwatch *z = createStopwatch();
    out << "\naaaaa_aaaaabhString\n";
    for (int j = 0; j < 2; ++j)
    {
        if (j == 0)
        {
            out << "\nTrivial\n";
        }
        else
        {
            out << "\nKMP\n";
        }

        out << "[";
        for (int h = 1; h <= 101; h += 10)
        {
            _string = "";
            for (int i = 0; i < h; ++i)
            {
                _string += "aaaaab";
            }
            z->reset();
            z->start();
            if (j == 0)
            {
                FindStringTrivial(_string, subString);
            }
            else
            {
                FindStringKMP(_string, subString);
            }
            z->stop();
            out << "[" << h << "," << z->getElapsed() << "],";
        }
        out << "]";
    }
}



int main(int argc, char **argv)
{
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}
